package 链表;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 *
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 */
public class _160_相交链表 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int cur = 0; //计算较长链表多的节点个数
        ListNode p1 = headA;
        ListNode p2 = headB;

        while(p1!=null){
            cur++;
            p1 = p1.next;
        }

        while(p2!=null){
            cur--;
            p2 = p2.next;
        }

        //当两个链表走到最后,如果两个指针相等，说明相交，不相等，说明不相交
        if(p1!=p2) return null;

        //相交的情况
        p1 = headA;
        p2 = headB;

        if(cur>0){
            //A比较长
            while(cur!=0){
                cur--;
                p1 = p1.next;
            }
        }else if(cur< 0){
            //B比较长
            while(cur!=0){
                cur++;
                p2 = p2.next;
            }
        }

        //当走完长的那段，开始共同走，直到两个节点相等
        while(p1!=p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}
